package codingforgreat.class17;


//lc:378
//有序矩阵最小第k值
public class Class02_KthSmallestElementInSortedMatrix {
    /*
    * 思路： 最小最大值2分
    * 找小于某个值距离该值最近的值
    * 每次求小于等于某个值的个数  个数：列数
    * 一直往下走，大就往左走不收集信息
    * */
    class Info{
        int res;
        int ans;

        public Info(int res, int ans) {
            this.res = res;
            this.ans = ans;
        }
    }

    public int kthSmallest(int[][] matrix, int k) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return  0;
        }
        int min = matrix[0][0];
        int max = matrix[matrix.length - 1][matrix[0].length - 1];
        int ans = 0;
        while(min <= max){
            int mid = (min + max) / 2;
            Info info = getAns(matrix, mid);
            if(info.ans >= k){
                ans = info.res;
                max = mid - 1;
            }else if(info.ans < k){
                min = mid + 1;
            }
        }
        return ans;
    }

    public Info getAns(int[][] matrix, int k){
        int N = matrix.length;
        int M = matrix[0].length;
        int j = M - 1;
        int i = 0;
        int ans = 0;
        int res = Integer.MIN_VALUE;
        while( i < N && j >= 0){
            if (matrix[i][j] <= k) {
                res = Math.max(res, matrix[i][j]);
                ans += j + 1;
                i++;
            } else {
                j--;
            }
        }
        return new Info(res,ans);
    }


}
